/*
 * @LastEditTime: 2023-03-23 20:06:33
 * @Method: 
 * @Description: 
 */
package Preview.tengxunyinyue;

import java.util.*;


public class Solution1 {
    int[][] dp;
    int minRes = Integer.MAX_VALUE;

    public int getValue (String str, int l, int r) {
        HashSet<Character> set = new HashSet<>();
        for (int i = l;i <= r;i++) {
            char c = str.charAt(i);
            set.add(c);
        }
        return set.size() * (r - l + 1);
    }
    
    public void dfs (String str, int start, int k, int curRes) {
        if (start >= str.length()) {
            return;
        }
        if (k == 1) {
            curRes = Math.max(curRes, dp[start][str.length() - 1]);
            minRes = Math.min(minRes, curRes);
            return;
        }
        for (int i = start; i < str.length();i++) {
            int item = dp[start][i];
            dfs(str, i + 1, k - 1, Math.max(curRes, item));
        }
    }

    public int getMaxValue (String str, int k) {
        int n = str.length();
        dp = new int[n][n];
        for (int i = 0;i < n;i++) {
            for (int j = i;j < n;j++) {
                if (i == j) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = getValue(str, i, j);
                }
            }
        }
        // for (int i = 0;i < n;i++) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }
        dfs(str, 0, k, 0);
        return minRes;
    }
}